1. Field of the Inventions
This invention relates to scalable multistage switching networks, specifically to the in-service method of adding one or more stages to a scalable multistage switching network.
2. Background Information
The addition of an extra stage to the design of a multistage interconnection network has numerous benefits to a switching network. The extra stage can be used to add fault tolerance. For example, FIG. 1 depicts an extra stage cube network which comprises extra stage 102 and hypercube network 104. If a failure occurs in a connection within the hypercube network, the extra stage can be used to route traffic around the fault. Traditionally, in an extra stage cube network the extra stage is activated only upon the detection of a fault.
Huang showed in U.S. Pat. No. 5,841,775, issued on Nov. 24, 1998 entitled “Scalable Switching Network” which is hereby incorporated by reference as if set forth in full, that in a redundant blocking compensated cyclic group (RBCCG) network extra rows can be added to the network to give fault tolerance and blocking tolerance to a switching network, by introducing additional paths within the network. Unlike the extra stage cube network, the extra rows in the RBCCG network are active at all times. With a proper routing algorithm, the network can automatically detect and reroute around any faults introduced by either a broken connection or a broken switching element.
In networks such as the RBCCG network as well as others, the degree of fault tolerance and blocking tolerance is often related to the number of extra stages within the network. As a result, there is a need to upgrade a network by adding stages. There are several approaches to upgrades.
In a “system down” upgrade where the network is shutdown, all connections between switching elements that need to be made in accordance to the desired post-upgrade topology can be made in any order at any time. For example, all connections can be disconnected and then new connections can be made in accordance with the desired post-upgrade topology. The network can then be restarted once the new post-upgrade topology is implemented. The draw back to this method is that the network is unusable during the upgrade process.
Prasad in U.S. Pat. No. 6,049,542, issued on Apr. 11, 2000 entitled “Scalable Multistage Interconnection Network Architecture and Method for Performing In-service Upgrade Thereof,” teaches an upgrade where a core section of switching elements can be “hot-swapped” out for an upgrade core section. By the use of a hot-swap, the network is in service during the upgrade. The draw back to this method is that multiplexers for use in the hot-swap must be in place. Additionally, a core section of switching elements must be taken out of service, so as more stages are desired, more hardware must be removed. For example, initially there might be one stage, which is then swapped for three stages, so initially one stage is removed. Then the three core stages might later be upgraded to five stages, leaving the three old stages removed. Even with reuse of hardware, this method is not economical as more and more stages are involved. Furthermore, this method is not readily compatible with other modes of upgrade such as a width upgrade or a fanout upgrade, which are available for some forms of switching networks such as described by Lu in U.S. patent application Ser. No. 10/074,174 filed on Feb. 10, 2002 entitled “Width Upgrade for a Scalable Switching Network”, which is hereby incorporated by reference as if set forth in full (henceforth referred to as the '174 application), and U.S. patent application Ser. No. 10/075,086 filed on Feb. 10, 2002 entitled “Fanout Upgrade for a Scalable Switching Network”, which is hereby incorporated by reference as if set forth in full,
Lu in U.S. patent application Ser. No. 09/897,263, filed on Jul. 2, 2001 entitled “Row Upgrade for a Scalable Switching Network” which is hereby incorporated by reference as if set forth in full, henceforth referred to as the '263 application, teaches an upgrade through the addition of extra stages in the middle of a redundant multistage interconnection network. As an example, FIG. 2A depicts a 24-port RBCCG switching network. In accordance with the '263 application, an insertion point between stage 202 and 204 is selected. Conceptually, as shown in FIG. 2B, new stage 206 and interconnection network 210a can be inserted between stage 202 and interconnection network 210. Although in reality, connections within interconnection network 210 have been disconnected and reformed as interconnection network 210b. Equivalently, new stage 206 could have been inserted between interconnection network 210 and stage 204, resulting in interconnection network 210a as the reformed instance of interconnection network 210 and interconnection network 210b as the newly introduced interconnection network.
Lu and Huang in U.S. patent application Ser. No. 10/786,874, filed on Feb. 24, 2004 entitled “Systems and Methods for Upgradeable Scalable Switching” which is hereby incorporated by, references as if set forth in full, henceforth referred to as the '874 application, extend the upgrade method to apply other types of network which are not technically redundant multistage network such as the network shown in FIG. 3 which is the result of the orthogonal overlay of two RBCCG networks, also referred to as a double RBCCG overlaid network. The method also is applicable to less traditional multistage networks such as the augmented shuttle exchange network shown in FIG. 4A, which is really a banyan network with additional connections between switching elements within each stage.
The upgrade methods described in the '263 application and the '874 application show a two phase process. The first phase inserts the new stage that preserves one adjacent interconnection network topology and produces a second interconnection network with parallel connections. Referring to FIG. 4B, new stage 406 is inserted between stages 402 and 404. In this example, interconnection network 410's topology is preserved and interconnection network 412 is introduced which has a set of parallel connections. After new stage 406 is properly inserted, in the second phase, interconnection network 412 is then rewired into the desired post-upgrade topology resulting in interconnection network 414, as shown in FIG. 4C. Though the new stage is now properly integrated into the new network completing the “row upgrade”, the new network is not complete. Finally, as shown in FIG. 4D, new intra-stage interconnections 416 are added to form an extended form of an augmented shuffle exchange network. Though in this example, intra-stage interconnections 416 are added after the insertion of the new stage, they can be added at any time since they are independent to the “row upgrade”. In fact, since they addition of these interconnections does not cause the breaking of any other connections, it is desirable to add them as soon as feasible as they can be used to bolster the fault tolerance of the network during the upgrade process.
The advantage of this upgrade method is that each connection that is broken and each connection that is made can be performed in a sequential manner. The fault tolerance of the network accommodates the broken connections, which occur during the upgrade process. While steps can still occur simultaneously, there is not overriding necessity of a simultaneous switch over as described by Prasad.
The intermediary phase of creating a set of parallel connections was designed to simplify the complexity of routing during the upgrade process and to prevent the loss of connectivity between any two external ports during the upgrade process. However, the price of this intermediary phase introduces additional steps during the upgrade process.
The methods disclosed herein address the elimination of the intermediary phase in a “stage upgrade”, that is an upgrade where one or more stages are added. Furthermore, in during more complex upgrade procedures where additional stages are added, the methods disclosed herein can be substituted for the splicing phase as described in the '874 application with the added benefit of eliminating additional rewiring steps.